Church integer
A representation of integers as functions invented by {Alonzo
Church}, inventor of {lambda-calculus}. The integer N is
represented as a {higher-order function} which applies a given
function N times to a given expression. In the {pure
lambda-calculus} there are no constants but numbers can be
represented by Church integers.
A {Haskell} function to return a given Church integer could be
written:
church n ◦ c
where
c f x ◦ if n ◦◦ 0 then x else c' f (f x)
where
c' ◦ church (n-1)
A function to turn a Church integer into an ordinary integer:
unchurch c ◦ c (:1) 0
See also {von Neumann integer}.
(1994-11-29)